package ext;
import java.util.*;
import org.junit.*;
public class NThreeSum {

    //n是否由连续的数三次方求和得到
    public static int[] nSum(int n) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 0);
        int i = 1, sum = 0;
        int[] nums = new int[n + 1];
        while (true) {
            if (i * i * i > n) {
                System.out.println(Arrays.toString(nums));
                return new int[]{-1, -1};
            }
            while (sum < n) {
                sum += i * i * i;
                nums[i] = sum;
                map.put(sum, i);
                i++;
            }
            int tar = sum - n;
            if (map.containsKey(tar)) {
                return new int[]{map.get(tar) + 1, i - 1};
            } else {
                int lo = 1, hi = i;
                while (lo < hi) {
                    int m = (hi - lo) / 2 + lo;
                    if (nums[m] < tar) {
                        lo = m + 1;
                    } else {
                        hi = m;
                    }
                }
                sum -= nums[lo];
            }
        }

    }

    public int nThree(int n) {
        return n * n * n;
    }

    public int nThreeSum(int i, int j) {
        int res = 0;
        for (int k = i; k <= j; k++) {
            res += nThree(k);
        }
        return res;
    }

    @Test
    public void test() {
        Random r = new Random();
        for (int k = 0; k < 100; k++) {
            int i = r.nextInt(100) + 5;
            int j = r.nextInt(100) + i;
            String res = Arrays.toString(nSum(nThreeSum(i, j)));
            String ori = Arrays.toString(new int[]{i, j});
            if (!res.equals(ori)) {
                System.out.println(ori);
            }
        }
    }

    @Test
    public void test2() {
        System.out.println( Arrays.toString(nSum(nThreeSum(90, 93))));
    }

}

/**
 [98, 105]
[37, 45]
[98, 142]
[56, 124]
[68, 99]
[41, 59]
[104, 151]
[14, 14]
[57, 124]
[83, 108]
[66, 163]
[74, 117]
[59, 125]
[62, 71]
[57, 129]
[75, 149]
[47, 63]
[72, 158]
[96, 178]
[93, 100]
[54, 96]
[20, 32]
[72, 143]
[104, 138]
[63, 153]
[64, 113]
[64, 148]
[60, 99]
[68, 91]
[67, 119]
[68, 70]
[54, 117]
[64, 103]
[96, 172]
[86, 146]
[57, 87]
[81, 164]
[41, 85]
[45, 98]
[38, 50]
[33, 37]
[67, 93]
[69, 117]
[40, 61]
[77, 151]
[84, 134]
[59, 67]
[60, 113]
[77, 89]
[90, 93]
[51, 116]
[30, 35]
[51, 111]
[61, 78]
[95, 106]
[71, 161]
[70, 156]
[64, 124]
[47, 86]
[84, 179]
[21, 21]
[79, 120]
[92, 156]
[51, 73]
[85, 124]
[92, 164]
[82, 136]
 
 
 */